// 给定一个二叉树的根节点root，要求：返回其最大路径和
// 路径：从树中的任意节点出发，沿着父节点-子节点连接，到达任意子节点的序列，同一个节点在一条路径上最多出现一次，该路径至少包含一个节点，且不一定经过根节点
// 路径和：路径中各节点值的总和

// 思路：后序遍历，先遍历左树和右树，然后以当前节点加上左右子节点和最大值比较并更新，然后进入下一轮递归，下一轮要选择左右子节点中较大的那个
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小
function maxPathSum(root) {
    let maxSum = -Infinity
    function dfs(root) {
        if (!root) {
            return 0
        }
        let leftVal = Math.max(dfs(root.left), 0) // 如果小于0则不会采纳
        let rightVal = Math.max(dfs(root.right), 0)
        maxSum = Math.max(maxSum, leftVal + rightVal + root.val)
        return root.val + Math.max(leftVal, rightVal) // 采纳较大的那个路径
    }
    dfs(root)
    return maxSum
}

const root = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
        },
        right: {
            val: 5,
        },
    },
    right: {
        val: -6,
    },
};

console.log(maxPathSum(root));